package GraphC;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by safe on 2017-04-01.
 * <p>
 * <p>
 * Floyd算法的基本思想：
 * （1）利用二维数组dist[i][j]记录当前vi到vj的最短路径长度，数组dist的初值等于图的带权邻接矩阵;
 * <p>
 * （2）集合S记录当前允许的中间顶点，初值S=Φ;
 * <p>
 * （3）依次向S中加入v0 ,v1… vn-1，每加入一个顶点，对dist[i][j]进行一次修正：设S={v0 ,v1… vk-1}，加入vk，则dist(k)[i][j] = min{ dist(k-1)[i][j]，dist(k-1)[i][k]+dist(k-1)[k][j]}。
 * dist(k)[i][j]的含义：允许中间顶点的序号最大为k时从vi到vj的最短路径长度。
 * <p>
 * dist(n-1)[i][j]就是vi到vj的最短路径长度。
 * <p>
 * <p>
 * 弗洛伊德（Floyd）算法求任意两点间的最短距离（JAVA）
 */
public class FloydInGraph {


    private static int INF = Integer.MAX_VALUE;

    //dist[i][j]=INF<==>i 和 j之间没有边

    private int[][] dist;

    //顶点i 到 j的最短路径长度，初值是i到j的边的权重

    private int[][] path;

    private List<Integer> result = new ArrayList<Integer>();

    public FloydInGraph(int size) {

        this.path = new int[size][size];
        this.dist = new int[size][size];

    }


    public void findCheapestPath(int begin, int end, int[][] matrix) {

        floyd(matrix);
        result.add(begin);
        findPath(begin, end);
        result.add(end);

    }


    public void findPath(int i, int j) {

        int k = path[i][j];
        if (k == -1) return;
        findPath(i, k);   //递归
        result.add(k);
        findPath(k, j);

    }

    public void floyd(int[][] matrix) {

        int size = matrix.length;
        //initialize dist and path
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                path[i][j] = -1;
                dist[i][j] = matrix[i][j];
            }
        }

        for (int k = 0; k < size; k++) {
            for (int i = 0; i < size; i++) {
                for (int j = 0; j < size; j++) {
                    if (dist[i][k] != INF &&
                            dist[k][j] != INF &&
                            dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                        path[i][j] = k;
                    }
                }
            }
        }
    }
    public static void main(String[] args) {

        FloydInGraph graph = new FloydInGraph(5);
        int[][] matrix = {
                {INF, 30, INF, 10, 50},
                {INF, INF, 60, INF, INF},
                {INF, INF, INF, INF, INF},
                {INF, INF, INF, INF, 30},
                {50, INF, 40, INF, INF},
        };

        int[][] matrix2 = {
                {0, 20, INF, INF, 20, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF},
                {20, 0, 30, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF},
                {INF, 30, 0, 20, INF, 30, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF},
                {INF, INF, 20, 0, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF},
                {20, INF, INF, INF, 0, 10, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF},
                {INF, INF, 30, INF, 10, 0, 20, 50, INF, INF, INF, INF, INF, INF, INF, INF, INF},
                {INF, INF, INF, INF, INF, 20, 0, 40, 10, INF, INF, INF, INF, INF, INF, INF, INF},
                {INF, INF, INF, INF, INF, 50, 40, 0, INF, 20, 20, INF, INF, INF, INF, INF, INF},
                {INF, INF, INF, INF, INF, INF, 10, INF, 0, 20, INF, INF, INF, 30, INF, INF, INF},
                {INF, INF, INF, INF, INF, INF, INF, 20, 20, 0, 20, INF, INF, INF, INF, INF, INF},
                {INF, INF, INF, INF, INF, INF, INF, 20, INF, 20, 0, 20, INF, INF, INF, INF, INF},
                {INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 20, 0, 10, INF, INF, INF, INF},
                {INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 10, 0, INF, INF, 20, INF},
                {INF, INF, INF, INF, INF, INF, INF, INF, 30, INF, INF, INF, INF, 0, 20, INF, INF},
                {INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 20, 0, 20, INF},
                {INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 20, INF, 20, 0, 40},
                {INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 40, 0}
        };

        int begin = 0;
        int end = 4;
        graph.findCheapestPath(begin, end, matrix);
        List<Integer> list = graph.result;
        System.out.println(begin + " to " + end + ",the cheapest path is:");
        System.out.println(list.toString());
        System.out.println(graph.dist[begin][end]);
    }




}
